#minimum word size constant
MIN_WORD_SIZE = 2

'''
' Class for creating a tree to load all the words into.
' We basically are creating separate trees for each first letter.
'''
class Node(object):
    #TODO: make sure the tiles aren't just letters but 'Tile' objects
    def __init__(self, letter='', final=False, depth=0):
        self.letter = letter
        self.final = final
        self.depth = depth
        self.children = {}
    
    #add a word to the tree
    def add(self, word):
        node = self
        #iterate through the word
        for index, letter in enumerate(word):
            #if the letter isn't a child, add a new node
            if letter not in node.children:
                node.children[letter] = Node(letter, index==len(word)-1, index+1)
            #set the current node to the child
            node = node.children[letter]
    
    #find anagrams in a given set of letters
    def find_anagrams(self, letters):
        tiles = {}
        #first, count how many of each letter we have
        for letter in letters:
            tiles[letter] = tiles.get(letter, 0) + 1
        #call a helper function to find anagrams
        #this returns a generator, so it will return each time it finds a word and then keep going
        return self._anagram(tiles, [], self, MIN_WORD_SIZE)
        
    #recursive helper function
    def _anagram(self, tiles, path, root, min_length):
        #if we're at the bottom of a tree, return it
        if self.final and self.depth >= MIN_WORD_SIZE:
            word = ''.join(path)
            #make sure we don't have spaces
            length = len(word.replace(' ', ''))
            if length >= min_length:
                yield word
        #otherwise go through it's children
        for letter, node in self.children.iteritems():
            count = tiles.get(letter, 0)
            #if the child isn't in the set of letters, keep going
            if count == 0:
                continue
            #mark the letter as used            
            tiles[letter] = count - 1
            
            #add it to the path
            path.append(letter)
            #keep going down this path, it will return only if it yields a result
            for word in node._anagram(tiles, path, root, min_length):
                yield word
            
            #pop the letter from the path
            path.pop()
            tiles[letter] = count